#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;



class Solution {
    public:
        vector<int> findSubstring(string S, vector<string> &L) {
            vector<int> ans;
            map<string, int> myMap;
            map<string, int> curMap;
            int count = 0;
            //cout << count << endl;
            int i;
            int wordSize = L[0].size();
            if (L.size() * wordSize > S.size()) return ans;
            for (i = 0; i < L.size(); i++) {
                if (myMap.count(L[i]) == 0)
                    myMap.insert(make_pair(L[i], 1));
                else
                    myMap[L[i]]++;
            }
            curMap = myMap;
            int lastPos = 1;
			bool start;
            for (i = 0; i < S.size(); ) {
                string str = S.substr(i, wordSize);
                if (curMap.count(str) == 0) {
                    count = 0;
                    curMap = myMap;
                    i = lastPos;
					lastPos++;
					start = true;
                    continue;
                } else {
                    if (curMap[str] > 0) {
                        //cout << "Match string: " << str << "at pos: " << i << endl;

                        curMap[str]--;
                        count++;
                        if (start) {
							start = false;
							lastPos = i+1;
						}
						 i += wordSize;
                    } else {
                        i = lastPos;
						lastPos++;
					    count = 0;
					    curMap = myMap;
                    }
                }
                if (count == L.size()) {
                    //cout << i << " " << endl;
                    ans.push_back(i-(L.size())*wordSize);
					count = 0;
					curMap = myMap;
					start = true;
                    i  = i+1-(L.size())*wordSize;

                }
            }
           // for (i = 0; i < ans.size(); i++)
             //   cout << ans[i] << " "  << endl;
            return ans;
        }
};


int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    string src = "abibibabbaaa";
    vector<string> match;
    match.push_back("a");
    match.push_back("b");
    match.push_back("b");
    vector<int> ans = mySolution.findSubstring(src, match);


    cout << "-----------------Test 2--------------------" << endl;
    //"mississippi", ["si","is"]
    string src2 = "mississippi";
    vector<string> match2;
    match2.push_back("si");
    match2.push_back("is");
    vector<int> ans2 = mySolution.findSubstring(src2, match2);



    cout << "-----------------Test 3--------------------" << endl;
    //"abababab", ["a","b","a"]
    string src3 = "abababab";
    vector<string> match3;
    match3.push_back("a");
    match3.push_back("b");
    match3.push_back("a");
    vector<int> ans3 = mySolution.findSubstring(src3, match3);


    cout << "-----------------Test 4--------------------" << endl;
    //"a", ["a"]
    string src4 = "a";
    vector<string> match4;
    match4.push_back("a");
    vector<int> ans4 = mySolution.findSubstring(src4, match4);


    cout << "-----------------Test 5--------------------" << endl;



}
